#include <iostream>

using namespace std;
struct TreeNode 
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int lowestCommonAncestor(TreeNode* root, int p, int q)
{
    int temp = root->val;
    if (p > q)
    {
        swap(p, q);
    }
    if ((p < temp && q > temp) || (p < temp && q == temp) || (p == temp && q > temp))
    {
        return temp;
    }
    else  if (p < temp && q < temp)
    {
        temp = lowestCommonAncestor(root->left, p, q);
    }
    else  if (p > temp && q > temp)
    {
        temp= lowestCommonAncestor(root->right, p, q);
    }
    return temp;
}

int main()
{
    TreeNode* node1 = new TreeNode(7);
    TreeNode* node2 = new TreeNode(1);
    TreeNode* node3 = new TreeNode(12);
    TreeNode* node4 = new TreeNode(0);
    TreeNode* node5 = new TreeNode(4);
    TreeNode* node6 = new TreeNode(11);
    TreeNode* node7 = new TreeNode(14);
    TreeNode* node8 = new TreeNode(3);
    TreeNode* node9 = new TreeNode(5);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;
    node5->left = node8;
    node5->right = node9;
    cout << lowestCommonAncestor(node1, 12, 11);
    return 0;
}